The present invention relates to a sort processing method and a sort processing apparatus, which, in a computer or data processing, compare magnitudes of pieces of data input by hardware, rearrange the pieces of data in accordance with a predetermined order and output the rearranged pieces of data.
Algorithms are adopted by software executed by a computer to carry out a sorting process as part of data processing. The easiness of programming of the software, the size of a memory for storing the programmed software and the shortness of a time required for execution of the software vary from algorithm to algorithm. A variety of examples of the algorithms include merge sort, bubble sort, heap sort and quick sort. The algorithm that is considered to be the most superior among them is the quick-sort algorithm.
These algorithms are each implemented as software executed by a computer sequentially. The performance of each algorithm is evaluated from the length of a time required to process a predetermined number of pieces of data being sorted, the number of repetitions of comparison and other criteria.
With the progress of semiconductor technologies and other progress represented by an LSI (Large Scale Integration), sort processing carried out so far by execution of software can now be performed by hardware as well.
The conventional hardware-based sort processing apparatus shown in FIG. 8 compares each input data in accordance with a diallel equation, and results of comparison are summed up. The sum is used as a priority level of the input data. Sort processing is then carried out by selecting input data in accordance with the priority level.
The sort processing apparatus shown in FIG. 8 is a matrix with signals lines from eight input terminals X1-(0) to X1-(7), each serving as a row stretched into the horizontal direction, and signals lines from eight input terminals Y1-(0) to Y1-(7), each serving as a column stretched into the vertical direction. The input terminals X1-(0) to X1-(7), each receive input data and the input terminals Y1-(0) to Y1-(7) also each receive input data.
The input terminals X1-(0) to X1-(7) receive pieces of input data 1-(0) to 1-(7) respectively. That is to say, input data received by an input terminal X1-(0) is denoted by reference numeral 1-(0), which is the input terminal's reference numeral X1-(0) excluding the alphabetic character X. By the same token, the input terminals Y1-(0) to Y1-(7) receive the same pieces of input data 1-(0) to 1-(7) respectively. That is to say, input data received by an input terminal Y1-(0) is denoted by reference numeral 1-(0), which is the input terminal's reference numeral Y1-(0) excluding the alphabetic character Y. Thus, the input terminal X1-(0) receives the input data 1-(0) which is also received by the input terminal Y1-(0).
The matrix of the sort processing apparatus is a matrix of comparators 2-(01) to 2-(07) compare the input data received by the input terminal X1-(0) with pieces of input data, which are received by the input terminals Y1-(1) to Y1-(07) respectively.
By the same token, the comparator 2-(10) and the comparators 2-(12) to 2-(17) compare the input data received by the input terminal X1-(1) with pieces of input data received by the input terminal Y1-(0) and the input terminals Y1-(2) to Y1-(7).
In the same way, the comparators 2-(20) to 2-(27) compare the input data received by the input terminal X1-(2) with pieces of input data received by the input terminals Y1-(0) to Y1-(7). Likewise, the comparators 2-(70) to 2-(76) compare the input data received by the input terminal X1-(7) with pieces of input data received by the input terminals Y1-(0) to Y1-(7).
An adder 3-(0) sums up comparison results of seven bits output by the comparators 2-(01) to 2-(07). By the same token, an adder 3-(1) sums up comparison results of seven bits output by the comparator 2-(10) and the comparators 2-(12) to 2-(17). In the same way, adder 3-(2) sums up comparison results of seven bits output by the comparators 2-(20) to 2-(27). Likewise, an adder 3-(7) sums up comparison results of seven bits output by the comparators 2-(70) to 2-(76) A converter 5 converts the priority levels D40 to D47 output by the adders 3-(0) to 3-(7) respectively into 3-bit priority signals D60 to D67 respectively. The 3-bit priority signals D60 to D67 each indicate which piece of input data is largest.
Multiplexers 7-(0) to 7-(7) each receive eight pieces of data through input terminals Z1-(0) to Z1-(7). These eight pieces of input data are the same pieces of input data supplied to the input terminals X1-(0) to X1-(7) and Y1-(0) to Y1-(7). That is to say, input data received by an input terminal Z1-(0) to Z1-(7) is denoted by reference numeral 1-(0) to 1-(7), which is the input terminal's reference numeral Z1-(i) excluding the alphabetic character Z or reference numerals X1-(0) to X1-(7) and Y1-(0) to Y1-(7) without the alphabetical characters X and Y respectively.
In accordance with the 3-bit priority signals D60 to D67 output by the converter 5, the multiplexers 7-(0) to 7-(7) each select one of the eight pieces of input data supplied to the input terminals Z1-(0) to Z1-(7). The multiplexers 7-(0) to 7-(7) select pieces of input data, which are different from each other, sorting the eight pieces of input data. The multiplexers 7-(0) to 7-(7) supply the sorted pieces of input data to output terminals 8-(0) to 8-(7) respectively.
In the configuration described above, the comparators 2-(01) to 2-(07) compare the magnitude of the input data received by the input terminal X1-(0) with the magnitudes of the pieces of input data received by the input terminals Y1-(1) to Y1-(7) respectively. If results of the comparison indicate that the magnitude of the input data received by the input terminal X1-(0) is smaller than the magnitudes of the pieces of input data received by the input terminals Y1-(1) to Y1-(7), the signals output by the comparators 2-(01) to 2-(07) will each be set to an active state to indicate the results of the comparison.
To put it concretely, the signals output by the comparators 2-(01) to 2-(07) are active if the results of the comparison indicate that the magnitude of the input data received by the input terminals X1-(0) to X1-(7) is smaller than the magnitudes of the pieces of input data received by the input terminals Y1-(0) to Y1-(7). For example, the signal output by the comparator 2-(01) is active if the result of the comparison indicates that the magnitude of the input data received by the input terminal X1-(0) is smaller than the magnitude of the input data received by the input terminal Y1-(1).
The comparison results output by the comparators 2-(01) to 2(07) are supplied to the adder 3-(0), which sums up active comparison results, generating a priority level D40 representing the sum of the active comparison results.
By the same token, the comparator 2-(10) to 2-(17) compare the input data received by the input terminal X1-(1) with pieces of input data received by the input terminal Y1-(0) to Y1-(7), outputting active or inactive signals representing the results of the comparison. In the same way, the comparators 2-(20) to 2-(27) compare the input data received by the input terminal X1-(2) with pieces of input data received by the input terminals Y1-(0) to Y1-(7), outputting active or inactive signals representing the results of the comparison. Likewise, the comparators 2-(70) to 2-(76) compare the input data received by the input terminal X1-(7) with pieces of input data received by the input terminals Y1-(0) to Y1-(6), outputting active or inactive signals representing the results of the comparison.
The comparison results output by the comparator 2-(10) to 2-(17) are supplied to the adder 3-(1), which sums up active comparison results, generating a priority level D41 representing the sum of the active comparison results. Likewise, the comparison results output by the comparators 2-(70) to 2-(76) are supplied to the adder 3-(7), which sums up active comparison results, generating a priority level D47 representing the sum of the active comparison results.
The converter 5 converts the priority levels D40 to D47 supplied thereto by the adders 3-(0) to 3-(7) respectively into 3-bit priority signals D60 to D67 respectively. The 3-bit priority signals D60 to D67 each indicate the size of each piece of input data.
In accordance with the 3-bit priority signals D60 to D67 output by the converter 5, the multiplexers 7-(0) to 7-(7) each select one of the eight pieces of input data supplied to the input terminals Z1-(0) to Z1-(7). The multiplexers 7-(0) to 7-(7) select pieces of input data, which are different from each other, sorting the eight pieces of input data, and supply the sorted pieces of input data to output terminals 8-(0) to 8-(7) respectively.
Assume that the number of pieces of input data to be compared is N. In this case, in general, the total number of comparison of input data is theoretically equal to the number of possible combinations of two pieces extracted from the N pieces of input as follows;The number of comparison of input data=N×(N−1)/2  (1)
However, since the conventional sort processing apparatus described above compares pieces of input data by using a matrix of comparators in accordance with a diallel equation, the number of required comparators is expressed as follows:The number of comparators=N×(N−1)  (2)
It is obvious that the number of comparators expressed by equation (2) is twice the minimum number of theoretically required comparators, which is expressed by equation (1).
In addition, after comparison, the sort processing apparatus carries out numerous kinds of rearrangement processing such as additions, conversion and multiplexing. It means that implementation of sort processing by hardware entails an increased circuit size. Furthermore, if the number of pieces of input data rises, not only does the circuit size increase, but the processing time also becomes longer as well.
Moreover, the circuit of the converter 5 for converting results of comparison is difficult to implement. Since the larger the number of pieces of input data is, the more complex the circuit of the converter 5 becomes, and there raises a problem of inconvenience encountered in the hardware implementation of the sort processing apparatus.